# Author    :Dun_Hz
# Time      :2024/3/15 15:25
# 找出一个列表中第k大或第k小的数
def partition(seq):
    pi = seq[0]
    lo = [x for x in seq[1:] if x <= pi]
    hi = [x for x in seq[1:] if x > pi]
    return pi,lo,hi
# 查找第k小的元素
def select_min(seq, k):
    pi, lo, hi = partition(seq)
    m = len(lo) #小于seq[0]的元素数量
    if m == k-1:
        return pi
    elif m < k-1:
        return select_min(hi, k-m-1)
    else:
        return select_min(lo, k)

# 查找第k大的元素
def select_max(seq, k):
    pi, lo, hi = partition(seq)
    m = len(hi) #大于seq[0]的元素数量
    if m == k-1:
        return pi
    elif m > k-1:
        return select_max(hi, k)
    else:
        return select_max(lo, m-k-1)

if __name__ =='__main__':
    seq = [3,4,1,6,3,7,9,13,93,0,100,1,2,2,3,3,2]
    print(select_min(seq, 3))
    print(select_min(seq, 1))
    print(select_max(seq, 3))
    print(select_max(seq, 1))